package com.ocean.greedy.medium;

/**
 * https://leetcode.cn/problems/jump-game-ii/
 * <p>
 * <p>
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * <p>
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 * <p>
 * 0 <= j <= nums[i]
 * i + j < n
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 * <p>
 * <p>
 * <p>
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 * 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
 * 示例 2:
 * <p>
 * 输入: nums = [2,3,0,1,4]
 * 输出: 2
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= nums.length <= 104
 * 0 <= nums[i] <= 1000
 * 题目保证可以到达 nums[n-1]
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/22 <br>
 */
public class JumpGameII {

    public static void main(String[] args) {
        JumpGameII jum = new JumpGameII();
        int[] nums = {2, 3, 1, 1, 4};
        int res = jum.jump(nums);
        System.out.println(res);
        int[] nums2 = {2, 3, 0, 1, 4};
        res = jum.jump(nums2);
        System.out.println(res);
    }

    public int jump(int[] nums) {
        // 贪婪思路：跳到下一个大的位置节点
        int m = nums.length;
        int i = 0;
        int time = 0;
        while (i < m) {
            int num = nums[i]; // num表示能够跳到的位置
            int temp = 0;
            time++;
            // 找到 i+1 到i+m中最大的值
            for (int j = 1; j <= num; j++) {
                if (i + j >= m) {
                    // 说明跳成功
                    return time;
                } else {
                    temp = Math.max(temp, (i + nums[j]));
                }
            }
            // 从下一个节点开始判断
            i = temp;
        }
        return time;
    }

    /**
     *
     *
     *
     * @param nums
     * @return
     */
    public int jump2(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            //找能跳的最远的
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if (i == end) { //遇到边界，就更新边界，并且步数加一
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

}
